package LK_Data_Structure;

import java.util.*;

public class DataS__Day_2 {
    /*两数之和
    * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，
    * 并返回它们的数组下标。
     解题思路:哈希表-*/
    public int[] twoSum(int[] nums, int target) {
        int[] array=new int[2];
        if (nums == null) {
            return array;
        }
        HashMap<Integer,Integer> hashMap=new HashMap<>();
        //将所有元素填入哈希表中
        for (int i = 0; i < nums.length; i++) {
            if (!hashMap.containsKey(nums[i])){
                hashMap.put(nums[i],i);
            }
        }
        //检查,相减后的元素是否存在,并判定不能重复
        for (int i = 0; i < nums.length; i++) {
            int k=target-nums[i];
            if (hashMap.containsKey(k) && i != hashMap.get(k) ){
                array[0]=i;
                array[1]=hashMap.get(k);
                break;
            }
        }
        return array;
    }

    /*合并两个有序数组
    * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
       请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。*/
    /*解法1:合并后排序*/
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k=0;
        for (int i = m; i < m+n ; i++) {
            nums1[i]=nums2[k];
            k++;
        }
        Arrays.sort(nums1);
    }
    /*解法2:双指针,利用已排序的性质,实现*/
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cut;

        while (p1 >= 0 || p2 >= 0){
            /*p1与p2为-1的情况代表该数组已经排完序*/
            if (p1 == -1){
                nums1[tail--]=nums2[p2--];
            }else if (p2 == -1){
                nums1[tail--]=nums1[p1--];
            }else if (nums1[p1] < nums2[p2]){
                nums1[tail--]=nums2[p2--];
            }else {
                nums1[tail--]=nums1[p1--];
            }
        }
    }


}
